package com.lw.leetcode.tree.b;

import com.lw.leetcode.linked.ListNode;

/**
 * Created with IntelliJ IDEA.
 * 2130. 链表最大孪生和
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/2 9:18
 */
public class PairSum {

    private ListNode p;

    public int pairSum(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        p = head;
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return getMaxPairSum(p1);
    }

    private int getMaxPairSum(ListNode node) {
        if (node == null) {
            return 0;
        }
        int maxPairSum = getMaxPairSum(node.next);
        maxPairSum = Math.max(node.val + p.val, maxPairSum);
        p = p.next;
        return maxPairSum;
    }


}
